An ad hoc communication system consists of a plurality of mobile wireless communication devices, also referred to herein simply as “devices”, “users” or “nodes”. Unlike a cellular telephone network, an ad hoc network does not rely on a set of fixed base stations to follow the movement of the devices or to route a connection between two devices. Since the transmission range of each device is limited, a device in the network can communicate directly only with other devices that are within its transmission range. Since the devices are mobile, the set of devices within the transmission range of a given device changes dynamically over time. Typically, devices continually enter and leave a given device's transmission range. Thus, as a device moves it may break communication with some devices while creating new connections with other devices. Every device periodically sends a “hello” message that is received by all devices within its transmission range. Every node receives hello messages from the nodes within its transmission range so that every node is periodically updated of the nodes within its transmission range.
The basic communication structure is therefore a dynamic graph in which each communication device is a node and an edge between two nodes indicates that the two nodes are in each other's transmission range. Each device can also act as a router by transferring speech or data packets from a first device in its range to a second device in its range when the first and second devices are not within each other's range. Thus, two devices can exchange speech packets only if there is a path of edges in the graph joining the two devices. Since new edges constantly emerge in the graph while other edges are deleted, a routing protocol is required that can cope with this dynamic situation, while attempting to optimize the allocation of device resources in order to maximize the amount and length of communication sessions available to the devices.
Ad hoc communication systems are classified according to the routing protocol that is used. In a table-driven routing protocol, each node maintains a table specifying a route to every other node in the network. When a first node (referred to herein as the “calling node”) initiates a session to a second node (referred to herein as the “called node”), the route from the calling node to the called node specified in the calling node's table is invoked.
In a search-driven routing protocol, for each communication session requested by a calling node, a search is performed to locate a path from the calling to the called node. The calling node broadcasts a route request packet to its neighbors. Every node receiving this request that is not the called node adds its own identity to the request and re-broadcasts the message to its neighbors. When the request reaches the called node, the full route appears in the message. Typically, each search requires flooding the network with search messages until the called node is reached and a routing path has been found. The algorithms in this class may need a quadratic number of messages (in the number of nodes) to perform a search for a route. The drawback of search driven protocols lies in the delay that occurs before a call session can start while the path search is being conducted.
The AODV (On-demand Distance Vector) routing algorithm (C. E. Perkins, and E. M. Royer. “Ad-hoc On-Demand Distance Vector Routing,” Second IEEE Workshop on Mobile Computing Systems and Applications, pp. 90-100, February 1999.) combines on demand search with recent destination routing information. A search for a route to a given called node is performed by flooding, but each node maintains a list of all its recent routings, so that the flooding can be reduced when it reaches an intermediate node that has the destination in its recent routing list. However, a burst of route request messages may flood the system especially in large condensed networks when many nodes try to create sessions simultaneously.
Another type of ad-hoc algorithm uses the GPS coordinates of each node to forward packets from one node to the neighboring node having the shortest Euclidian distance to the destination. The routing is oblivious and thus potentially more efficient than the one used in the AODV type of algorithm. Using GPS can be regarded as a way of assigning grid coordinates in the field to every node and using the grid metric to select the shortest routing paths.
Rao et al. (A. Rao, S. Ratnasamy, C. Papadimitrou, S. Shenker, I. Stoica, “Geographic Routing withhout Location Information”, ACM MobiCom 2003.) discloses use of virtual coordinates that approximate geographical coordinates without using GPS. The nodes are embedded in a grid wherein Euclidian distances in the plane are replaced by connectivity distances in the dynamic communication graph. The algorithm has three stages: 1) the nodes on the perimeter are identified, 2) the virtual coordinates of the perimeter are computed, and 3) based on the perimeter, virtual coordinates of internal nodes are computed. Virtual coordinates are computed using a relaxation method wherein each node updates its coordinates based on the coordinates of its neighbors.